def heapsort(arr):
    """
    堆排序
    """
    n = len(arr)
    #创建最大堆
    for i in range(arr //2 -1 ,-1,-1):
        heapify(arr, n, i)

    #交换最大元素并重新调整堆
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)        


def heapify(arr ,n ,i):
    largest = i
    left = i *2 +1
    right = i *2 +2

    if left < n and arr[left]>arr[largest]:
        largest = left
    if right < n and arr[right]> arr[largest]:
        largest = right

    if largest is not i:
        arr[largest],arr[i] = arr[i], arr[largest]
        heapify(arr, n ,largest)